package solution;

import java.util.*;

/**
 * DepthFirstOrder.java
 * @param <V>
 * -----------------------------------------------------
 *
 * Depth-first search vertex ordering in a digraph
 *
 * Three vertex orderings are of interest in typical applications:
 * - Preorder : Put the vertex on a queue before the recursive calls.
 * - Postorder : Put the vertex on a queue after the recursive calls.
 * - Reverse postorder : Put the vertex on a stack after the recursive calls.
 *
 * 注意：preorder其实记录了顶点的递归调用的顺序；postorder记录了顶点的递归调用返回的顺序；
 */
public class DepthFirstOrder<V> {
    private Set<V> marked;

    private Queue<V> pre; // vertices in preorder

    private Queue<V> post; // vertices in postorder

    private Deque<V> reversePost; //vertices in reverse postorder

    public DepthFirstOrder(Graph<V> graph) {
        this.marked = new HashSet<>();
        this.pre = new LinkedList<>();
        this.post = new LinkedList<>();
        this.reversePost = new ArrayDeque<>();

        for (V v : graph.vertices()) {
            if (!marked.contains(v)) {
                dfs(graph, v);
            }
        }
    }

    private void dfs(Graph<V> graph, V v) {
        pre.add(v);
        marked.add(v);
        for (Edge<V> edge : graph.neighbors(v)) {
            V w = edge.getTo();
            if (!marked.contains(w)) {
                dfs(graph, w);
            }
        }
        post.add(v);
        reversePost.push(v);
    }

    public Iterable<V> pre(){
        return pre;
    }

    public Iterable<V> post(){
        return post;
    }

    public Iterable<V> reversePost(){
        return reversePost;
    }
}
